package leetcode;

/**
 * 给定一个有序整数数组，元素各不相同且按升序排列，编写一个算法，创建一棵高度最小的二叉搜索树。
 * 示例:
 * 给定有序数组: [-10,-3,0,5,9],
 * 一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：
 * 0
 * / \
 * -3   9
 * /   /
 * -10  5
 *
 * @author TANGYE
 * @2021/1/14 16:48
 */
public class MinBinSearchTree {

    TreeNode root;

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public TreeNode createTree(int[] nums, int start, int end) {
        if (end < start) {
            return null;
        }
        // 因为要高度平衡，所以去中位数当根节点
        int mid = (start + end) / 2;
        // 用mid分割的两个数字，分别构建左右子树
        TreeNode node = new TreeNode(nums[mid]);
        // 构建左子树
        node.left = createTree(nums, start, mid - 1);
        // 构建右子树
        node.right = createTree(nums, mid + 1, end);
        return node;
    }


}
